/**
 * 学习 STL Algorithm 之查找算法
 * 
*/

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

bool isEven(int n) {
    return n % 2 == 0;
}

/* 测试 std::find() */
void testFind() {
    vector<int> vec = {1, 2, 3, 4, 5};
    auto it = find(vec.begin(), vec.end(), 3);
    if (it != vec.end()) {
        cout << "Found " << *it << " at position " << (it - vec.begin()) << endl;
    } else {
        cout << "Not found" << endl;
    }
}

/* 测试 std::find_if(), std::find_if_not() */
void testFindIf() {
    vector<int> vec = {1, 2, 3, 4, 5, 6, 7, 8, 9};
    vector<int> even;
    vector<int> odd;
    auto it = vec.begin();
    while(it != vec.end()) {
        it = find_if(it, vec.end(), isEven);
        if(it != vec.end()) {
            even.push_back(*it);
            ++it; // 这里必须++，否则下次找到的还是那个数
        }
    }
    it = vec.begin();
    while(it != vec.end()) {
        it = find_if_not(it, vec.end(), isEven);
        if(it != vec.end()) {
            odd.push_back(*it);
            ++it;
        }
    }
    cout << "所有的偶数：";
    for(auto e : even)
        cout << e << " ";
    cout << endl;
    cout << "所有的奇数：";
    for(auto e : odd)
        cout << e << " ";
    cout << endl;
}

/* 测试 std::find_end() */
void testFindEnd() {
    // 从后往前找子序列
    std::vector<int> vec = {1, 2, 3, 4, 5, 2, 3, 4, 5};
    std::vector<int> subVec = {2, 3};
    auto it = std::find_end(vec.begin(), vec.end(), subVec.begin(), subVec.end());
    if (it != vec.end()) {
        std::cout << "找到位置: " << (it - vec.begin()) << std::endl;
    } else {
        std::cout << "未找到" << std::endl;
    }

    std::string str = "hello world, hello universe";
    std::string subStr = "hello";
    auto it3 = std::find_end(str.begin(), str.end(), subStr.begin(), subStr.end());
    if (it3 != str.end()) {
        std::cout << "找到位置: " << (it3 - str.begin()) << std::endl;
    } else {
        std::cout << "未找到" << std::endl;
    }
}

/* 测试 std::search() */
void testSearch() {
    // 从前往后找子序列
    std::vector<int> vec = {1, 2, 3, 4, 5, 2, 3, 4, 5};
    std::vector<int> subVec = {2, 3};
    auto it = std::search(vec.begin(), vec.end(), subVec.begin(), subVec.end());
    if (it != vec.end()) {
        std::cout << "找到位置: " << (it - vec.begin()) << std::endl;
    } else {
        std::cout << "未找到" << std::endl;
    }

    std::string str = "hello world, hello universe";
    std::string subStr = "hello";
    auto it3 = std::search(str.begin(), str.end(), subStr.begin(), subStr.end());
    if (it3 != str.end()) {
        std::cout << "找到位置: " << (it3 - str.begin()) << std::endl;
    } else {
        std::cout << "未找到" << std::endl;
    }
}

int main() {
    testFindEnd();
    testSearch();
    return 0;
}
